package com.future;

import com.future.util.TreeNode;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

/**
 * Description: 1367. 二叉树中的链表
 *
 * @author weiruibai.vendor
 * Date: 2022/12/29 10:28
 */
public class Solution_1367 {

    private static Solution_1367 instance = new Solution_1367();

    public static void main(String[] args) {
        /**
         * [1,4,2,6], root = [1,4,4,null,2,2,null,1,null,6,8,null,null,null,null,1,3]
         *
         * [4,2,8] ,  root = [1,4,4,null,2,2,null,1,null,6,8,null,null,null,null,1,3]
         */
        TreeNode root = new TreeNode(1);
        root.left = new TreeNode(4);
        root.left.right = new TreeNode(2);
        root.left.right.left = new TreeNode(1);

        root.right = new TreeNode(4);
        root.right.left = new TreeNode(2);
        root.right.left.left = new TreeNode(6);
        root.right.left.right = new TreeNode(8);
        root.right.left.right.left = new TreeNode(1);
        root.right.left.right.right = new TreeNode(3);

        ListNode head = new ListNode(4);
        head.next = new ListNode(2);
        head.next.next = new ListNode(8);
        // head.next.next.next = new ListNode(6);
        //System.out.println(instance.isSubPath_v1(head, root));
        System.out.println(instance.isSubPath_v2(head, root));
    }

    /**
     * OK
     *
     * @param head
     * @param root
     * @return
     */
    public boolean isSubPath_v2(ListNode head, TreeNode root) {
        Map<Integer, List<TreeNode>> map = new HashMap<>();
        buildMap(root, map);
        ListNode tmp;
        int first = head.val;
        List<TreeNode> treeNodes = map.get(first);
        for (TreeNode node : treeNodes) {
            tmp = head;
            if (processIsSubPath(node, tmp)) {
                return true;
            }
        }
        return false;
    }

    private boolean processIsSubPath(TreeNode node, ListNode tmp) {
        if ((node == null && tmp == null) || tmp == null) {
            return true;
        }
        if (node == null) {
            return false;
        }
        ListNode op = tmp;
        if (node.val == tmp.val) {
            if (processIsSubPath(node.left, tmp.next) || processIsSubPath(node.right, op.next)) {
                return true;
            }
        }
        return false;
    }


    private void buildMap(TreeNode root, Map<Integer, List<TreeNode>> map) {
        if (root == null) {
            return;
        }
        int val = root.val;
        List<TreeNode> orDefault = map.getOrDefault(val, new ArrayList<TreeNode>());
        orDefault.add(root);
        map.put(val, orDefault);
        buildMap(root.left, map);
        buildMap(root.right, map);
    }

    /**
     * 超时
     *
     * @param head
     * @param root
     * @return
     */
    public boolean isSubPath_v1(ListNode head, TreeNode root) {
        if (head == null) {
            return false;
        }
        return process(head, root, head);
    }

    private boolean process(ListNode head, TreeNode root, ListNode tmp) {
        if (tmp == null) {
            return true;
        }
        if (root == null) {
            return false;
        }
        if (root.val == tmp.val) {
            tmp = tmp.next;
            boolean b1 = process(head, root.left, tmp);
            if (b1) {
                return true;
            }
            boolean b2 = process(head, root.right, tmp);
            if (b2) {
                return true;
            }
        }
        ListNode op = head;
        if (process(head, root.left, op) || process(head, root.right, op)) {
            return true;
        }
        return false;
    }
}
